The present invention relates generally to the field of wireless communications and specifically to a method for efficient multicast of data over wireless cellular networks.
The transfer of large amounts of information from one source to a plurality of destinations is of immense and growing importance. Traditional broadcast models (e.g., radio and television) are limited in both selection and time. That is, only a finite selection of content may be broadcast at any given time, and additionally all receivers must access the relevant transmission channel at the same time to receive a complete copy of the information.
One variation on the broadcast model, which exploits large transmission channel bandwidth, ameliorates these problems to some degree in a limited form of multicast. For example, the five most popular two-hour movies may be broadcast on separate cable television channels, and successively rebroadcast at 20-minute intervals. A subscriber may then select a movie and, if his or her selection is within the set of movies being multicast, be directed to the channel on which that movie is next scheduled to be broadcast. The subscriber would then experience a 0-20 minute delay (with an average delay of 10 minutes) before the movie begins. While this offers the subscriber some degree of choice in selection of the content, and the appearance of near-on-demand reception, the selection is limited to a relatively small subset that must be predicted by the broadcaster, and the initial delay can be significant. The scheme also requires extensive transmission channel bandwidth (30 channels for the example described), and either increasing the content selection or decreasing the perceived delay requires the allocation of additional channels.
Computer networks, such as the Internet, offer new options for transferring information from one or more sources to a plurality of destinations. Internet distribution allows for a larger degree of content selection on part of each recipient, and additionally reduces the start-up delay experienced by the recipient. The Internet, however, was initially developed to transfer low-volume and delay-tolerant data, such as e-mail and similar text files, static graphics, and hypertext information such as web page descriptions. Significant limitations constrain the transfer of large data volume and/or delay-intolerant content, such as digital video and audio information. Typical Internet data distribution comprises dividing the content into segments or packets, and transferring the packets through the network under a standard protocol, such as the Transfer Control Protocol/Internet Protocol (TCP/IP). To ensure reliable transfer of the data across the network, these protocols include an acknowledgement mechanism, whereby data receivers acknowledge the successful transfer of each packet back to the information source, and unacknowledged packets are assumed lost and retransmitted. While such protocols provide for robust data integrity, they may introduce significant delay and severely constrain the bandwidth of a particular data transmission, particularly as the acknowledge response times increase due to network distance between the source and destination. Additionally, the ability of a data broadcast source, or server, to provide content to a large plurality of users, or clients, is constrained by the server resources, as each data transfer connection typically requires the establishment of a separate TCP session, requiring allocation of memory and processing power. Thus, the ability of a large plurality of users to select and receive content from a given server is severely constrained.
To address these limitations on information delivery, it is known in the art to utilize particular classes of Forward Error Correction (FEC) encoding schemes, and to transmit the encoded packets outside of the constraints of traditional control protocols such as TCP/IP. In particular, some classes of FEC codes exhibit a specific characteristic, such that if enough of the encoded symbols are successfully received and decoded, regardless of which ones they are or in which order they are received, the original information may be reconstructed. For example, suppose K information symbols (i.e., sequences of bits in the information data) are encoded into a code word of N transmission symbols, where N greater than K, and Nxe2x88x92K indicates the amount of redundancy added by the encoding process. The key requirement of the coding process is that the K information symbols can be reconstructed from any K out of the N transmission symbols, regardless of which K symbols are received.
One class of FEC codes that satisfies this key requirement exactly is called Reed-Solomon codes, which are well known in the art. Reed-Solomon codes are commonly employed, for example, in retrieving data from a storage medium such as an audio CD, where scratches or other imperfections may preclude receiving a precise copy of the stored data. The decoding of Reed-Solomon has been extensively studied. Efficient implementations of Reed-Solomon decoders have been developed, particularly in hardware.
A class of FEC codes that nearly satisfies the key coding requirement are referred to as Tornado codes. Using Tornado codes, K information symbols may be constructed from K+A of the N transmission symbols, where A is small relative to K (for example, A=5K has been shown to be an effective value of A). These codes are less efficient, and require the reception of more transmission symbols to reconstruct the original information, than do Reed-Solomon codes. However, they are believed to be less computationally complex, and require less memory and fewer compute resources to implement in software, especially for very large block lengths. Tornado codes are described in Byers, et al., A Digital Fountain Approach to Reliable Distribution Of Bulk Data, ACM SIGCOMM (1998).
With the growth and technical sophistication of wireless communications services, wireless communications are widely anticipated to move beyond voice, paging, and e-mail content, and additionally to distribute graphic and multimedia content. The wireless communication network may be viewed as simply the last leg in the transmission across a conventional computer network, such as for example when a user accesses an Internet site from a wireless mobile terminal, and elects to receive multimedia content being multicast by the web server. In this scenario, since the wireless communication link exhibits erasure and error characteristics that are significantly different from the wire line Internet, increased efficiency may be realized by addressing the characteristics of the multicast as applied to the unique transmission medium. In the case where a wireless network server is itself the source of a multicast, and concomitantly has greater control over the formatting and transmission of the information, even greater efficiencies may be obtained.
The present invention includes a method of multicasting data over a wireless cellular communication network. The data, comprising K information symbols, is encoded to form a codeword of N transmission symbols, where N greater than K, in such a way that the K information symbols can be recovered from any K+A of the N transmission symbols. The N transmission symbols are transmitted from a base station in the wireless cellular communication network to a plurality of mobile terminals over a communication channel.
The encoding process may be such that A=0. The redundancy Nxe2x88x92K may be chosen to provide adequate reception performance at the edge of the base station""s cell. The redundancy may be chosen in response to channel quality information. The base station may vary the transmission power of the transmission symbols in response to channel quality information. Retransmission requests from a plurality of mobile terminals may be consolidated, and one or more transmission symbols retransmitted in response to the retransmission requests. The level of error correction coding and/or the transmission power may be adjusted in response to retransmission requests. Transmission symbols may be transmitted from different antennae or on different frequency hopping patterns.
The data may be divided into segments, each segment encoded separately, and transmission symbols from each encoded segment broadcast over a separate communication channel, which may be a TDMA time slot, a CDMA spreading encoding, an FDMA frequency, or a frequency hopping pattern.
The data may be encoded, and a plurality of transmission symbols transmitted in a first communication channel, with redundant transmission symbols transmitted in a second communication channel.
If a mobile terminal receiving information in a multicast is handed off to another base station, it may continue to receive transmission symbols, if they are being multicast in the second base station. If not, the second base station may begin to multicast the information from the beginning, or it may multicast only transmission symbols not received by the mobile terminal from the first base station.